The basic methods, which are used in peer-to-peer (P2P) computing, have many useful properties, which make them ideal candidates to form the basis of large distributed systems and grid systems: scalability, fault tolerance and self-organization. In P2P systems, the boundary between the role of a user and that of a service provider is blurred. When a user enters a P2P system, he also becomes active as a service provider at the same time, and thus increases the overall capacity of the system. As a result, the system also scales as the number of memories changes dynamically. In P2P systems, a stable, reliable overall system is formed by means of equal individual components, namely read-write memories, which can also be referred to as memories for short. The memories are connected via communication links and can go out of action independently of one another and without any prior notice, which means that they are unreliable. Unreliability of memories can be caused either by communication faults, which mean that one memory can no longer be reached by other memories, or by a fault or a decision made by one memory no longer to react to queries from other memories. New memories can be added to the system at any time.
One significant problem in the field of P2P computing is that of constructing, on the basis of unreliable memories, a reliable global data structure, in which objects can be stored and retrieved.
An object in this context consists of a name and a list of attributes. Objects may represent anything, for example may contain the address or the details of users, computers, networks, services or other objects. A name may be of any data type, but is usually a string of characters or a number. An attribute in turn consists of an attribute name and an attribute value, which may also be of any data type. Objects, which do not fit into this scheme, can easily be modeled thereon by storing the entire content of the object as an attribute “content”. A list of attributes belonging to an object having the name “Martin Schmidt” could therefore appear as follows: (“First name”, “Martin”), (“Surname”, “Schmidt”), (“Street”, “Main Street”), (“House number”, “42”), (“Postcode”, “12345”), (“Town”, “Berlin”).
Hereinafter a distinction will be made between two types of search processes: name service and directory service. A name service offers mapping between names and attributes. The name service makes it possible, for a given name, to query all the attributes of the corresponding object.
A directory service is the opposite of the name service. In this case a search for objects is carried out on the basis of one or more of their attributes. The result is a list of names. With a directory service, it is possible to respond to questions of the following type: “Show me all PDF documents, which are stored on this computer and which were written by Donald Knuth prior to 1995”. A directory service is similar to the yellow pages. Microsoft's Active Directory Services, X.500 and the leaner variant LDAP are typical examples.
In order to scale to several million memories and to tolerate the addition/removal of memories, without any loss of functionality or efficiency, a distribution scheme is required, which specifies which objects are stored on which memory or memories, and also a routing method, which makes it possible to find the memories, which have stored the objects when a search is carried out for the latter. To this end, such a system generally comprises three components: a search processor, a routing layer and a database.
The search processor receives queries and maps the queries onto the underlying routing layer. Simple queries such as “Martin Schmidt” for example are forwarded directly, whereas more complex queries, such as the abovementioned query concerning the PDF documents written by Knuth, are broken down into a number of steps, which are worked through individually.
The routing layer is located between the search processor and the database. It is required in distributed systems in order to find the memories, which contain the required objects. In the Domain Name Service (DNS) of the Internet, which finds the respective Internet address in relation to computer names, the routing layer is implemented for example as a hierarchy of memories. Starting from a central memory, the responsibility branches in a number of steps to other memories until the memory, which has stored the object sought is reached. For routing in P2P systems, use is made for example of chordal graphs or multidimensional tori or hypercubes.
The database contains the actual objects of a memory.
Existing systems and methods for routing in P2P systems, such as Network Flooding (Gnutella), Superpeer Networks (KaZaA, FastTrack), unstructured routing with caching for anonymous file sharing (Freenet), Skip Lists (Chord, DKS), tree-like data structures (Kademlia, Pastry, Tapestry), multidimensional coordinate spaces (CAN) and a few others, differ from one another in terms of efficiency and scalability. In particular, the higher the number of communications that are necessary between memories via communication links in order to find objects, the more negative the effect on efficiency.
Many current P2P systems are based on distributed hash tables (DHTs) and chordal graphs. When a new object is stored, its name is converted into a numerical value by means of the hash function. Using the routing method, the memory, which is responsible for this value, is then determined, and the object is then entered in the database in this memory. Objects are found by analogy as follows: the name of the object sought is converted into a numerical value by means of the hash function, and the memory responsible for said numerical value is determined by means of the routing method. The object can then be read from the database of this memory.
For the routing method, each memory has a so-called routing table containing information as to how other memories can be contacted. The routing table has a limited size and contains the communication links to O(log(N) other memories, where N is the number of memories in the overall system.
The use of a hash function has to date been deemed necessary in most systems in order thereby to prevent any overloading of memories, which are responsible for common names, since the hash function distributes the names equally. However, so-called range queries, in which it is not the exact name but rather only a prefix of the name, which is given, are thus impossible since names that are similar to one another are scattered widely over the system by hash functions. Moreover, these systems are based on the theory of consistent hashing (cf. D. Karger et al., “Consistent hashing and random trees: Distributed caching protocols for relieving hot spots on the World Wide Web”, in Proceedings of the 29th Annual ACM Symposium on Theory of Computing (El Paso, Tex., May 1997), pages 654-663), which takes only insufficient account of the properties of the systems in terms of efficiency and scalability. One known system, which supports range queries, but guarantees the efficiency of routing performance only with a certain level of probability is Mercury (cf. A. Bharambe et al.: “Mercury: Supporting Scalable Multi-Attribute Range Queries”, SIGCOMM 2004, Portland, August 2004). The administrative complexity in Mercury for dynamically adapting the routing tables to the load distribution in the system is based on estimation rules for the load of other memories and is disproportionately high.